//实现平衡二叉树
class AVLTree{
    constructor(data,height=0){
        this.data = data;
        this.left = null;
        this.right = null;
        this.height = height;
    }

    static isAVLTree(T){
        if(!(T instanceof AVLTree)){
            throw new Error("type error")
        }
    }

    static getHeight(T){
        if(T instanceof AVLTree) return T.height;
        else return -1;
    }

    updateHeight(){
        this.height = Math.max(AVLTree.getHeight(this.left),AVLTree.getHeight(this.right))+1;
    }

    //LL旋
    static SingleLeftRotation(A){
        AVLTree.isAVLTree(A);
        let B = A.left;
        A.left = B.right;
        B.right = A;
        A.updateHeight();
        B.updateHeight();
        return B;
    }

    //LR旋
    static LeftRightRotation(A){
        AVLTree.isAVLTree(A);
        A.left = AVLTree.SingleRightRotation(A.left);
        return AVLTree.SingleLeftRotation(A);
    }

    //RR旋
    static SingleRightRotation(A){
        AVLTree.isAVLTree(A);
        let B = A.right;
        A.right = B.left;
        B.left = A;
        A.updateHeight();
        B.updateHeight();
        return B;
    }

    //RL旋
    static RightLeftRotation(A){
        AVLTree.isAVLTree(A);
        A.right = AVLTree.SingleLeftRotation(A.right);
        return AVLTree.SingleRightRotation(A);
    }

    static insertData(){
        let tree = new AVLTree(arguments[0]);
        for (let index = 1; index < arguments.length; index++) {
            tree = tree.insert(arguments[index]);
        }
        return tree;
    }

    static insert(T,X){
        if(!T){
            T = new AVLTree(X);
        }else if(X<T.data){
            T.left = AVLTree.insert(T.left,X);
            T.left.updateHeight();
            if(AVLTree.getHeight(T.left)-AVLTree.getHeight(T.right)===2){
                if(X<T.left.data)
                    T = AVLTree.SingleLeftRotation(T);
                else
                    T = AVLTree.LeftRightRotation(T);
            }
        }else if(X>T.data){
            T.right = AVLTree.insert(T.right,X);
            T.right.updateHeight();
            if(AVLTree.getHeight(T.left)-AVLTree.getHeight(T.right)===-2){
                if(X>T.right.data)
                    T = AVLTree.SingleRightRotation(T);
                else
                    T = AVLTree.RightLeftRotation(T);
            }
        }
        T.updateHeight();
        return T;
    }

    insert(data){
        return AVLTree.insert(this,data);        
    }

    find(data){
        if(this.data===data){
            return true;
        }else if(data < this.data){
            if(this.left) return this.left.find(data);
            else return false;
        }else{
            if(this.right) return this.right.find(data);
            else return false;
        }
    }
}


  //测试数据
  let tree = AVLTree.insertData(2,3,8,6,5,1,20,12,14,16,17,19);
//   const avl = new AVLTree([2,3,8,6,5,1,20,12,14,16,17,19])
  console.log(tree);
debugger